package JZ_Offer.algorithm.dp;

import java.util.Arrays;

/**
 * 跳台阶扩展问题
 * <p>
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
 * 动态规划dp，贪心算法
 *
 * @Author piper
 * @Date 2019/11/12 2:01 下午
 */
public class JZ71_变态跳台阶 {

    /**
     * 本质上是斐波那契数列的变种，普通跳台阶是一步与两步，问题规模缩小到分成最后要跳到第 n 阶可以跳两次或者一次去求解，
     * 所以，在普通跳台阶，设置两个临时变量存下跳一次或者两次时，前面会有多少种可能的结果
     * dp 就是可以由什么状态推导出最后的状态，斐波那契数列是由前两种状态，而这里就是由前 n - 1 种状态推导出
     * <p>
     * 这里用同一个套路来分析一下
     * 若楼梯阶级 n = 3
     * 跳 3 步到 3：没有剩下步数没跳的，只有这样一种跳法
     * 跳 2 步到 3：剩下的是第一步没跳，起始跳到第一步只有一种
     * 跳 1 步到 3：剩下的是第二步没跳，起始跳到第二步有两种
     * 求得，n = 3 时，有 4 种跳法
     * <p>
     * 若楼梯阶级 n = 4
     * 跳 4 步到 4：没有剩下步数没跳的，只有这样一种跳法
     * 跳 3 步到 4：剩下的是第一步没跳，起始跳到第一步只有一种
     * 跳 2 步到 4：剩下的是第二步没跳，起始跳到第二步只有两种
     * 跳 1 步到 4：剩下的是第三步没跳，起始跳到第三步有四种
     * 求得，n = 4 时，有 8 种跳法
     * <p>
     * 若楼梯阶级 n = n
     * 跳 x 步到 n 有几种的和，跟前 n - 1 种状态有关
     */
    public int JumpFloorII(int target) {
        if (target <= 2) {
            return target;
        }
        int[] dp = new int[target + 1];
        Arrays.fill(dp, 1); //初始化每一种都可以直接从 0 跳到 n
        dp[0] = 0; //从 0 跳到 0 为 0 种，因为 n = 0，没法跳
        for (int i = 2; i <= target; i++) {
            for (int j = i - 1; j >= 1; j--) {
                dp[i] += dp[j]; //第 n 个状态是由前 n - 1 种状态推导出来，就是累加！
            }
        }
        return dp[target];
    }

    /**
     * 设nn 级台阶有f(n)f(n) 种跳法，根据最后一次跳台阶的数目可以分解为最后一次一级，则前面需要跳n-1n−1 级，有f(n-1)f(n−1) 种跳法；最后一次跳两级，则前面需要跳n- 2n−2 级，有f(n-2)f(n−2) 种跳法。以此类推 易知，
     * $f(n)=f(n-1)+f(n-2)+……f(0)\\ f(n-1)=f(n-2)+……f(0)f(n)=f(n−1)+f(n−2)+……f(0)
     * f(n−1)=f(n−2)+……f(0)$
     * 两式相减得，
     * <p>
     * f(n)=2f(n-1)f(n)=2f(n−1)
     */
    public int JumpFloorII1(int target) {
        return 1 << (target - 1);
        //return (int)Math.pow(2,target-1);
    }
}
